LeetCode 19、删除链表的倒数第 N 个结点

一、题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1 输出：[]

示例 3：

输入：head = [1,2], n = 1 输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

二、题目解析

一般来说，链表相关的算法题考察的知识点有以下几个：

• 递归
• 反转
• 双指针
• 环

本题解题思路如下：

1、再原链表的前面添加一个虚拟头结点，使得原链表的头结点和其余的结点地位一样，进行删除操作时不需要进行区分处理。

2、在原链表的头部设置一个指针 former，使用 for 循环让它向后移动 n 步。

3、在原链表的头部再设置一个指针 cur，同时在虚拟头结点位置设置一个指针 latter。

4、接下来，同时让这三个指针向后移动，直到 former 指向了 null，此时 cur 指向的恰好就是倒数第 n 个结点。

5、由于 latter 一直在 cur 的上一个结点位置，这个时候只需要让 latter 指向 cur 的下一个结点，那么也就完成了删除 cur 结点的操作。

三、参考代码

// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 添加表头
        ListNode dummy = new ListNode(-1);

        dummy.next = head;

        // 寻找需要删除的节点节点
        ListNode cur = head;

        // 指针 latter 指向虚拟头结点
        ListNode latter = dummy;

        ListNode former = head;

        // 让 former 指针先向前走 n 步
        for (int i = 0 ; i < n; i++) {
            // former 指针向后移动
            former = former.next;
        }

        // 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
        while (former != null) {
            // former 指针向后移动
            former = former.next;

            // latter 来到 cur 的位置
            latter = cur;

            // cur 指针向后移动
            cur = cur.next;
        }

        // 删除 cur 这个位置的结点
        latter.next = cur.next;

        // 返回虚拟头结点的下一个结点
        return dummy.next;
    }
}

Python

# 本题文字版详解请访问下方网站
# https://www.algomooc.com
# 作者：程序员吴师兄
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 添加表头
        dummy = ListNode(-1)
        dummy.next = head

        # 寻找需要删除的节点节点
        cur = head

        # 指针 latter 指向虚拟头结点
        latter = dummy

        former = head

        # 让 former 指针先向前走 n 步
        for i in range(n):
            # former 指针向后移动
            former = former.next

        # 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
        while former is not None:
            # former 指针向后移动
            former = former.next

            # latter 来到 cur 的位置
            latter = cur

            # cur 指针向后移动
            cur = cur.next

        # 删除 cur 这个位置的结点
        latter.next = cur.next

        # 返回虚拟头结点的下一个结点
        return dummy.next